package com.leetcode.algorithm.y19.m04;

import java.util.List;
import java.util.Stack;

/**
 * leetcode-cn.com
 * 
 * (done)64. 最小路径和
 * (done)71. 简化路径
 * (done)120. 三角形最小路径和
 * (done)931. 下降路径最小和
 * @author: jie.deng
 * @time: 2019年4月4日 上午10:34:54
 */
public class MySolution0404 {
    
    /**
     * 64. 最小路径和
     * 
     * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     * 
     * 说明：每次只能向下或者向右移动一步。
     * 
     * 示例:
     * 
     * 输入:
     * [
     *   [1,3,1],
     *   [1,5,1],
     *   [4,2,1]
     * ]
     * 输出: 7
     * 解释: 因为路径 1→3→1→1→1 的总和最小。
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        // 动态规划算法
        int rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        int cols = grid[0].length;
        // 动态规划
        // 第一行节点grid[0][col] += grid[0][col - 1]
        // 第一列节点grid[row][0] += grid[row-1][0]
        // 后续行节点grid[row][col] += Math.min(grid[row][col - 1], grid[row - 1][col])
        for (int col = 1; col < cols; col++) {
            grid[0][col] += grid[0][col - 1];
        }
        for (int row = 1; row < rows; row++) {
            grid[row][0] += grid[row - 1][0];
            for (int col = 1; col < cols; col++) {
                grid[row][col] += Math.min(grid[row][col - 1], grid[row - 1][col]);
            }
        }
        return grid[rows - 1][cols - 1];
    }
    
    /**
     * 71. 简化路径
     * 
     * 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
     * 
     * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
     * 
     * 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入："/home/"
     * 输出："/home"
     * 解释：注意，最后一个目录名后面没有斜杠。
     * 示例 2：
     * 
     * 输入："/../"
     * 输出："/"
     * 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
     * 示例 3：
     * 
     * 输入："/home//foo/"
     * 输出："/home/foo"
     * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
     * 示例 4：
     * 
     * 输入："/a/./b/../../c/"
     * 输出："/c"
     * 示例 5：
     * 
     * 输入："/a/../../b/../c//.//"
     * 输出："/c"
     * 示例 6：
     * 
     * 输入："/a//b////c/d//././/.."
     * 输出："/a/b/c"
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
        if (path == null || path.length() == 0) {
            return "/";
        }
        Stack<String> stack = new Stack<>();
        String[] pathArr = path.split("/");
        for (String str : pathArr) {
            if ("..".equals(str)) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (".".equals(str) || "".equals(str)) {
                continue;
            } else {
                stack.push(str);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            if (sb.length() > 0) {
                sb.insert(0, "/");
            }
            sb.insert(0, stack.pop());
        }
        sb.insert(0, "/");
        return sb.toString();
    }
    
    /**
     * 120. 三角形最小路径和
     * 
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     * 
     * 例如，给定三角形：
     * 
     * [
     *      [2],
     *     [3,4],
     *    [6,5,7],
     *   [4,1,8,3]
     * ]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     * 
     * 说明：
     * 
     * 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        // 动态规划
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int size = triangle.size();
        List<Integer> preList = triangle.get(0);
        for (int i = 1; i < size; i++) {
            List<Integer> list = triangle.get(i);
            list.set(0, list.get(0) + preList.get(0)); // 每行第一个元素
            int levelSize = list.size();
            list.set(levelSize - 1, list.get(levelSize - 1) + preList.get(levelSize - 2));// 每行最后一个元素
            for (int j = 1; j < levelSize - 1; j++) {
                list.set(j, list.get(j) + Math.min(preList.get(j - 1), preList.get(j)));// 中间元素
            }
            preList = list;
        }
        int min = preList.get(0);// 找最后一行的最小值
        for (Integer num : preList) {
            if (num < min) {
                min = num;
            }
        }
        return min;
    }
    
    /**
     * 931. 下降路径最小和
     * 
     * 给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
     * 
     * 下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
     * 
     *  
     * 
     * 示例：
     * 
     * 输入：[[1,2,3],[4,5,6],[7,8,9]]
     * 输出：12
     * 解释：
     * 可能的下降路径有：
     * [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
     * [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
     * [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
     * 和最小的下降路径是 [1,4,7]，所以答案是 12。
     * 
     *  
     * 
     * 提示：
     * 
     * 1 <= A.length == A[0].length <= 100
     * -100 <= A[i][j] <= 100
     * @param A
     * @return
     */
    public int minFallingPathSum(int[][] A) {
        int rows = A.length;
        if (rows == 0) {
            return 0;
        }
        int cols = A[0].length;
        if (cols == 1) {
            return A[0][0];
        }
        for (int row = 1; row < rows; row++) {
            A[row][0] += Math.min(A[row - 1][0], A[row - 1][1]);
            for (int col = 1; col < cols - 1; col++) {
                A[row][col] += Math.min(Math.min(A[row - 1][col], A[row - 1][col - 1]), A[row - 1][col + 1]);
            }
            if (cols > 1) {
                A[row][cols - 1] += Math.min(A[row - 1][cols - 1], A[row - 1][cols - 2]);
            }
        }
        int min = A[rows - 1][0];
        for (int col = 1; col < cols; col++) {
            if (A[rows - 1][col] < min) {
                min = A[rows - 1][col];
            }
        }
        return min;
    }
}
